package 回溯;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @ClassName _131分割回文串
 * @Description TODO
 * @Author 昝亚杰
 * @Date 2021/10/11 19:51
 * Version 1.0
 **/
public class _131分割回文串 {
    //合并测试
    List<List<String>> listss = new ArrayList<List<String>>();
    List<String> list = new ArrayList<>();
    public List<List<String>> partition(String s) {
        getPartition(s, 0);
        return listss;
    }
    public void getPartition(String s, int start){
        if(start == s.length()){
            listss.add(new ArrayList<>(list));
            return ;
        }
        for(int i = start; i < s.length(); i++){
            if(isPatition(s, start, i)){
                list.add(s.substring(start,i + 1));
                getPartition(s, i + 1);
                list.remove(list.size()-1);
            }
        }
    }
    public boolean isPatition(String s, int start, int end){
        if(start == end){
            return true;
        }
        for(; start < end; start++,end--){
            if(s.charAt(start) != s.charAt(end)){
                return false;
            }
        }
        return true;

    }
}
